package Tree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 108.将有序数组转换为二叉搜索树
 * 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。
 */
public class sortedArrayToBST {
    /**
     * 一刷，写法较为复杂，建议看二刷
     */
    public TreeNode sortedArrayToBST(int[] nums) {

        if(nums == null || nums.length == 0) return null;
        TreeNode root = new TreeNode(nums[nums.length/2]);
        root.left =  sortedArrayToBST(splitnums(nums,nums.length/2).get(0));
        root.right =  sortedArrayToBST(splitnums(nums,nums.length/2).get(1));
        return root;
    }
    public static List<int[]> splitnums(int[] nums, int index) {
        List<int[]> res = new ArrayList<>();

        int[] left = new int[index];
        int[] right = new int[nums.length - index - 1];
        for (int i = 0; i < left.length; i++) {
            left[i] = nums[i];
        }
        for (int i = 0; i < right.length; i++) {
            right[i] = nums[index + i + 1];
        }
        res.add(left);
        res.add(right);
        return res;
    }


    /**
     * 二刷
     */
    public TreeNode sortedArrayToBST2(int[] nums) {
        if (nums.length == 0 || nums == null) {
            return null;
        }
        int length = nums.length;
        TreeNode root = new TreeNode(nums[length / 2]);
        root.left = sortedArrayToBST(Arrays.copyOfRange(nums, 0, length / 2));
        root.right = sortedArrayToBST(Arrays.copyOfRange(nums, length / 2 + 1, length));
        return root;
    }

    /**
     * hot100一刷
     * hot100二刷
     */
    class Solution {
        public TreeNode sortedArrayToBST(int[] nums) {
            if (nums == null || nums.length == 0) {
                return null;
            }
            int index = nums.length / 2;
            TreeNode root = new TreeNode(nums[index]);
            root.left = sortedArrayToBST(Arrays.copyOfRange(nums, 0, index));
            root.right = sortedArrayToBST(Arrays.copyOfRange(nums, index + 1, nums.length));
            return root;
        }
    }
}
